/*
 *  bm.c
 *  StringSearch
 *
 *  Created by Mohammad H. Afrasiabi on 09-12-14.
 *  Copyright 2009 UBC. All rights reserved.
 *
 *	Code is greatly influenced by Boyer-Moore algorithm in:
 *	http://www-igm.univ-mlv.fr/~lecroq/string/node14.html
 *
 */

#include <math.h>

#include "bm.h"

int		bmGs[GSIZE], bmBc[BSIZE];
char *	_pattern;
int		_patternSize;


int max(int a, int b)
{
	return (a>b?a:b);
}

void preBC(char *pattern, int patternSize, int bmBc[]) 
{
	int i;
	
	for (i = 0; i < BSIZE; ++i)
		bmBc[i] = patternSize;
	for (i = 0; i < patternSize - 1; ++i)
		bmBc[pattern[i]] = patternSize - i - 1;
}


void suffixes(char *pattern, int patternSize, int *suffix) 
{
	int  i, j, k;
	
	suffix[patternSize - 1] = patternSize;
	k = patternSize - 1;
	for (i = patternSize - 2; i >= 0; --i) 
	{
		if (i > k && suffix[i + patternSize - 1 - j] < i - k)
			suffix[i] = suffix[i + patternSize - 1 - j];
		else
		{
			if (i < k)
				k = i;
			j = i;
			while (k >= 0 && pattern[k] == pattern[k + patternSize - 1 - j])
				--k;
			suffix[i] = j - k;
		}
	}
}

void preGS(char *pattern, int patternSize, int bmGs[]) 
{
	int i, j, suffix[GSIZE];
	
	_pattern		= pattern;
	_patternSize	= patternSize;
	
	suffixes(pattern, patternSize, suffix);
	
	for (i = 0; i < patternSize; ++i)
		bmGs[i] = patternSize;
	j = 0;
	for (i = patternSize - 1; i >= 0; --i)
		if (suffix[i] == i + 1)
			for (; j < patternSize - 1 - i; ++j)
				if (bmGs[j] == patternSize)
					bmGs[j] = patternSize - 1 - i;
	for (i = 0; i <= patternSize - 2; ++i)
		bmGs[patternSize - 1 - suffix[i]] = patternSize - 1 - i;
}


void BM_Init(char *pattern, int patternSize)
{
	preGS(pattern, patternSize, bmGs);
	preBC(pattern, patternSize, bmBc);
	
}

void BM_Search(char *text, int textSize) 
{
	int i, j;
	
	j = 0;
	while (j <= textSize - _patternSize) 
	{
		for (i = _patternSize - 1; i >= 0 && _pattern[i] == text[i + j]; --i);
		
		if (i < 0) 
		{
			ADD_RESULT(j);
			j += bmGs[0];
		}
		else
			j += max(bmGs[i], bmBc[text[i + j]] - _patternSize + 1 + i);
	}
}
